COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	To ``standardize'' a PDA, constructed as a flowchart using these components:
C00003 00003
C00004 00004
C00006 00005
C00007 00006
C00011 ENDMK
C⊗;
To ``standardize'' a PDA, constructed as a flowchart using these components:

	START

            		ACCEPT			REJECT




	READ			   EOF?			WRITE X


   a     b     EOF	    true         false




	PUSH X (0 or 1)	      POP		     EMPTY?   		TOP


			0      1   Empty          true   false	    0    1   Empty


Stage 1:  Make these replacements.



		Original				Modified


		 START				 	START


						 	push #



		 READ				   	EOF?


	      a   b   EOF		      	 false        true


					     	 READ


					      a        b




		 POP			      		POP

	    0     1   Empty		   	    0    1    #


							    push #




		EMPTY?			      		POP


	   true      false	    	      0          1          #

				  	   push 0     push 1     push #




		TOP			      		POP


	   0     1   Empty	      		0        1	#

				    	     push 0   push 1   push #


Stage 2:

Modify so that the PDA never makes a redundant test of EOF.  Make three copies of
the flowchart; which one the program is in depends on whether the value of EOF is
true, false, or unknown.  EOF tests are bypassed if the result is known; if
resulting loops are empty, they are replaced by REJECT.  A READ enters the region
where EOF is unknown; an EOF enters one of the regions where EOF is known.

Stage 3:

Eliminate a PUSH if it leads, without further PUSHing or branching (branching means
READ or EOF or a non-deterministic choice) to a POP.

Example:					 READ


						  a


	PUSH 1		PUSH 0		WRITE A		WRITE B		POP


			This one can				      0     1
			be eliminated.



   becomes					READ


						 a


        PUSH 1				WRITE A		WRITE B		POP


					WRITE B			     0      1


Repeat until no longer applicable.  Replace any non-branching loop by REJECT.

Stage 4:


Replace ACCEPT by



	EOF		    false		  READ		   a,b


        true		     POP		  0,1


			      #			  ACCEPT


Similar for REJECT.

After Stage 1, the operations used are:

START, ACCEPT, REJECT.
READ*, EOF
WRITE
PUSH, POP*

where READ* never tries to read with empty input, and POP* never tries to pop
an empty stack.  There is always a # at the bottom of the stack.

After Stage 2, the algorithm, on input of length N, never executes READ more than
N times, nor EOF more than N+1 times.

Any computation which runs forever must eventually consist entirely of WRITE, PUSH,
and POP.

After Stage 3, if the PDT is deterministic, every PUSH must lead without branching
to a READ, ACCEPT, or REJECT.  At this point, there is no way a computation can
run forever:

(1) It can't have infinitely many READs or EOFs, as shown above.
(2) It can't have infinitely many PUSHes, or it would READ infinitely often.
(3) It can't have infinitely many POPs, or it would be trying to POP an empty stack.
(4) All that remains is WRITEs; since they don't branch, they must belong, 
    eventually, to a non-branching loop, which would have been replaced by REJECT.

So, after Stage 3, a DPDT must terminate.  After Stage 4, a terminating computation
of a PDT must empty the input and stack; a DPDT will always terminate, with input
and stack empty.

If the original automaton was deterministic, we can now just exchange ACCEPT and
REJECT to get a DPDT accepting the complementary language.

If  L  is a DPDA language, so is its complement, and its complement is therefore,
like L, a CFL.  Therefore CFL's whose complements are not CFL's, although accepted
by NPDA's, can't be accepted by DPDA's.  An example of a CFL whose complement is
not a CFL is the complement of {a b c }.  Also, languages accepted by DPDA's have an
unambiguous grammar, so if a language or its complement is inherently ambiguous
(example: {a b c }+{a b c }), the language if not a DCFL.

154A01[1,rwf]